package lk;

import java.util.*;

public class D2310012 {
    // 雇佣 K 位工人的总代价

    // 两个小根堆, 模拟每一轮的雇佣
    // 时间：O(nlogn)
    // 空间：O(n)
    public long totalCost(int[] costs, int k, int candidates) {
        PriorityQueue<Integer> q1 = new PriorityQueue<Integer>();
        PriorityQueue<Integer> q2 = new PriorityQueue<Integer>();

        int n = costs.length;
        int left = candidates;
        int right = Math.max(candidates - 1, n - candidates - 1);
        // candidates - 1 是数量不超过 2 * candidates 的情况

        long ans = 0;
        // 将前 candidates 人的佣金加入小根堆中
        for (int i = 0; i < candidates; i++) q1.add(costs[i]);
        // 将后 candidates 人的佣金加入小根堆中 (后面可能没有 candidates 人)
        for (int i = n - 1; i > right; i--) q2.add(costs[i]);

        // 模拟每一轮雇佣
        while (k-- > 0) {
            if (!q1.isEmpty() && !q2.isEmpty()) {
                // 前后两个小根堆都不空, 选择其中一个较小出队
                // 然后双指针向中间靠拢, 继续将新的工人加入小根堆
                if (q1.peek() <= q2.peek()) {
                    ans += q1.poll();
                    if (left <= right) q1.add(costs[left++]);
                } else {
                    ans += q2.poll();
                    if (left <= right) q2.add(costs[right--]);
                }
            } else if(q2.isEmpty()) {
                ans += q1.poll();
                if (left <= right) q1.add(costs[left++]);
            } else if (q1.isEmpty()) {
                ans += q2.poll();
                if (left <= right) q2.add(costs[right--]);
            }
        }

        return ans;
    }


    // 倒排链求交
    public int[] intersectionAndSort (int[] docList1, int[] docList2) {
        int i = docList1.length - 1;
        int j = docList2.length - 1;
        ArrayList<Integer> list = new ArrayList<>();
        while (i >= 0 && j >= 0) {
            if (docList1[i] == docList2[j]) {
                list.add(docList1[i]);
                i--;
                j--;
            } else if (docList1[i] > docList2[j]) {
                i--;
            } else {
                j--;
            }
        }
        int[] res = new int[list.size()];
        for (int k = 0; k < res.length; k++) {
            res[k] = list.get(k);
        }
        return res;
    }

    // 不同路径
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    // 第一行 和 第一类, 只有一种路径
                    dp[i][j] = 1;
                } else {
                    // 上面一格的路径数 + 左边一格的路径数
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}
